home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 423_01 / bspline / bspline.cpp < prev   
Encoding:
C/C++ Source or Header  |  1994-03-10  |  5.4 KB  |  200 lines
  1. /*********************************************************************
  2.  
  3.  Simple b-spline curve algorithm
  4.  
  5.  Copyright 1994 by Keith Vertanen (vertankd@cda.mrs.umn.edu)
  6.  
  7.  Released to the public domain (your mileage may vary)
  8.  
  9. **********************************************************************/
  10.  
  11. #include <graphics.h>
  12. #include <stdlib.h>
  13.  
  14. struct point {
  15.   double x;
  16.   double y;
  17.   double z;
  18. };
  19.  
  20. int set_graph(void);
  21. void compute_intervals(int *u, int n, int t);
  22. double blend(int k, int t, int *u, double v);
  23. void compute_point(int *u, int n, int t, double v, point *control,
  24.            point *output);
  25.  
  26. void bspline(int n, int t, point *control, point *output, int num_output)
  27.  
  28. /*********************************************************************
  29.  
  30. Parameters:
  31.   n          - the number of control points minus 1
  32.   t          - the degree of the polynomial plus 1
  33.   control    - control point array made up of point stucture
  34.   output     - array in which the calculate spline points are to be put
  35.   num_output - how many points on the spline are to be calculated
  36.  
  37. Pre-conditions:
  38.   n+2>t  (no curve results if n+2<=t)
  39.   control array contains the number of points specified by n
  40.   output array is the proper size to hold num_output point structures
  41.  
  42.  
  43. **********************************************************************/
  44.  
  45. {
  46.   int *u;
  47.   double increment,interval;
  48.   point calcxyz;
  49.   int output_index;
  50.  
  51.   u=new int[n+t+1];
  52.   compute_intervals(u, n, t);
  53.  
  54.   increment=(double) (n-t+2)/(num_output-1);  // how much parameter goes up each time
  55.   interval=0;
  56.  
  57.   for (output_index=0; output_index<num_output-1; output_index++)
  58.   {
  59.     compute_point(u, n, t, interval, control, &calcxyz);
  60.     output[output_index].x = calcxyz.x;
  61.     output[output_index].y = calcxyz.y;
  62.     output[output_index].z = calcxyz.z;
  63.     interval=interval+increment;  // increment our parameter
  64.   }
  65.   output[num_output-1].x=control[n].x;   // put in the last point
  66.   output[num_output-1].y=control[n].y;
  67.   output[num_output-1].z=control[n].z;
  68.  
  69.   delete u;
  70. }
  71.  
  72. void main()
  73. {
  74.   int *u;
  75.   int n,t,i;
  76.   n=7;          // number of control points = n+1
  77.   t=4;           // degree of polynomial = t-1
  78.  
  79.   point *pts;          // allocate our control point array
  80.   pts=new point[n+1];
  81. /*
  82.   randomize();
  83.   for (i=0; i<=n; i++)  // assign the control points randomly
  84.   {
  85.       (pts[i].x)=random(100)+(i*600/n);
  86.       (pts[i].y)=random(500);
  87.       (pts[i].z)=random(500);
  88.   }
  89. */
  90.   pts[0].x=10;  pts[0].y=100;  pts[0].z=0;
  91.   pts[1].x=200;  pts[1].y=100;  pts[1].z=0;
  92.   pts[2].x=345;  pts[2].y=300;  pts[2].z=0;
  93.   pts[3].x=400;  pts[3].y=250;  pts[3].z=0;
  94.   pts[4].x=500;  pts[4].y=550;  pts[4].z=0;
  95.   pts[5].x=550;  pts[5].y=150;  pts[5].z=0;
  96.   pts[6].x=570;  pts[6].y=50;   pts[6].z=0;
  97.   pts[7].x=600;  pts[7].y=100;  pts[7].z=0;
  98.  
  99.   int resolution = 100;  // how many points our in our output array
  100.   point *out_pts;
  101.   out_pts = new point[resolution];
  102.  
  103.   bspline(n, t, pts, out_pts, resolution);
  104.   if (set_graph())
  105.   {
  106.     setcolor(69);
  107.     for (i=0; i<=n; i++)
  108.       circle(pts[i].x,pts[i].y,2); // put circles at control points
  109.     circle(pts[0].x,pts[0].y,0);  // drop the pen down at first control point
  110.     for (i=0; i<resolution; i++)
  111.     {
  112.       setcolor(i);   // have a little fun with the colors
  113.       putpixel(out_pts[i].x,out_pts[i].y,WHITE);
  114.     }
  115.   }
  116. }
  117.  
  118. double blend(int k, int t, int *u, double v)  // calculate the blending value
  119. {
  120.   double value;
  121.  
  122.   if (t==1)            // base case for the recursion
  123.   {
  124.     if ((u[k]<=v) && (v<u[k+1]))
  125.       value=1;
  126.     else
  127.       value=0;
  128.   }
  129.   else
  130.   {
  131.     if ((u[k+t-1]==u[k]) && (u[k+t]==u[k+1]))  // check for divide by zero
  132.       value = 0;
  133.     else
  134.     if (u[k+t-1]==u[k]) // if a term's denominator is zero,use just the other
  135.       value = (u[k+t] - v) / (u[k+t] - u[k+1]) * blend(k+1, t-1, u, v);
  136.     else
  137.     if (u[k+t]==u[k+1])
  138.       value = (v - u[k]) / (u[k+t-1] - u[k]) * blend(k, t-1, u, v);
  139.     else
  140.       value = (v - u[k]) / (u[k+t-1] - u[k]) * blend(k, t-1, u, v) +
  141.           (u[k+t] - v) / (u[k+t] - u[k+1]) * blend(k+1, t-1, u, v);
  142.   }
  143.   return value;
  144. }
  145.  
  146. void compute_intervals(int *u, int n, int t)   // figure out the knots
  147. {
  148.   int j;
  149.  
  150.   for (j=0; j<=n+t; j++)
  151.   {
  152.     if (j<t)
  153.       u[j]=0;
  154.     else
  155.     if ((t<=j) && (j<=n))
  156.       u[j]=j-t+1;
  157.     else
  158.     if (j>n)
  159.       u[j]=n-t+2;  // if n-t=-2 then we're screwed, everything goes to 0
  160.   }
  161. }
  162.  
  163. void compute_point(int *u, int n, int t, double v, point *control,
  164.             point *output)
  165. {
  166.   int k;
  167.   double temp;
  168.  
  169.   // initialize the variables that will hold our outputted point
  170.   output->x=0;
  171.   output->y=0;
  172.   output->z=0;
  173.  
  174.   for (k=0; k<=n; k++)
  175.   {
  176.     temp = blend(k,t,u,v);  // same blend is used for each dimension coordinate
  177.     output->x = output->x + (control[k]).x * temp;
  178.     output->y = output->y + (control[k]).y * temp;
  179.     output->z = output->z + (control[k]).z * temp;
  180.   }
  181. }
  182.  
  183.  
  184. int set_graph(void)
  185.   {
  186.     int graphdriver = DETECT, graphmode, error_code;
  187.  
  188.     //Initialize graphics system; must be EGA or VGA
  189.     initgraph(&graphdriver, &graphmode, "c:\\borlandc\\bgi");
  190.     error_code = graphresult();
  191.     if (error_code != grOk)
  192.         return(-1);               // No graphics hardware found
  193.     if ((graphdriver != EGA) && (graphdriver != VGA))
  194.     {
  195.         closegraph();
  196.         return 0;
  197.     }
  198.     return(1);                   // Graphics OK, so return "true"
  199. }
  200.